The control logic for a cache manages all aspects of cache accesses including hits, misses, victims, etc. A high performance cache design attempts to minimize the number of stalls that result from the cache control logic. One aspect of cache control logic that can introduce stalls into the pipeline is allocating new lines into the cache.
An N-way set-associative cache consists of M sets, where each set is a collection of N ways. Way is synonymous with cache line and represents a contiguous range of bytes stored in the cache. The data for each way of a cache is uniquely identified by a collection of bits called a tag. When allocating a new cache line into the cache, the control logic first locates a set and way where the cache line will reside. Once a set and way have been identified, the line currently residing there is evicted. If the line is dirty, it is written back to the next level of the memory hierarchy. The data for the new line is requested from the memory hierarchy by a read request also known as an allocate request. An outstanding allocate request is one in which the allocate request has been presented to the memory hierarchy but data has not yet returned to the cache control logic.
The number of outstanding allocate requests that the cache control logic can maintain at any given time is a design decision dependent on several factors: buffer size in the master for recording requests; buffer size in the slave for recording requests; the number of unique transaction IDs allowed at the next level of the memory hierarchy; and the number of ways in each set of the cache The number of ways in each set is a fixed property of the cache design. In a typical cache controller, the number of outstanding allocate requests to the same set is limited to the number of ways in the set. In a four-way set-associative cache, there can be four outstanding allocate requests to any given set. Once the number of outstanding allocate requests to the same set reaches the limit, any further allocate requests will stall the pipeline.